const treeData = require("./treeData")

//基于栈结构深度优先遍历树并复制(深拷贝)一颗树，下面的算法会在原树的每个子节点中新增一个parent属性
//如果需要不修改原树中的数据，可以后面在添加一个方法，把原树中的parent属性删掉，或者在新创建子节点挂到其父节点之后，把原树中的对应节点的parent属性删除
function copyTreeByDepthStack(node){
    if(!node){
        return null
    }
    const stack = []
    stack.push(node)
    let newNode = {value:null,children:null}
    let parent = null
    while(stack.length > 0){
        const currentNode = stack.pop()
        const tempNode ={value:currentNode.value,children:[]}
        tempNode.value = currentNode.value
        currentNode.parent && currentNode.parent.children.push(tempNode)
        currentNode.parent && delete currentNode.parent     //删除当前节点的parent属性，将原树恢复
        if(!parent){
            newNode.value = tempNode.value
            newNode.children = []
        }else{
           
        }
        if(currentNode.children.length > 0){
            parent = !parent ?  newNode : tempNode   //当前节点为子节点，其下面还存在子节点
            for(let i = currentNode.children.length-1;i >= 0;i--){
                //在原树的每个节点中增加一个属性，记录新树中对应当前节点的父节点，方便后面新创建的节点能够添加到相应节点的下面，在节点的属性中没有新增parent属性
                currentNode.children[i].parent = parent     
                stack.push(currentNode.children[i])     //子元素从后往前遍历入栈
            }
        }
       
    }
    return newNode

}

function testCopyTreeByDepthStack(){
    const tree = treeData.getTree()
    const newTree =  copyTreeByDepthStack(tree)
    console.log("newTree:",newTree)
}
testCopyTreeByDepthStack()